package arithmetic.demo3;


/**
 * 题目： 暴搜_单词搜索
 */

class Solution {

    // 上下左右坐标移动
    private int[] row = { 0, 0, -1, 1 };
    private int[] col = { -1, 1, 0, 0 };

    // 记录路径
    private boolean[][] checkPath;

    // 宽度
    private int n;
    private int m;

    public boolean exist(char[][] board, String word) {

        // 初始化
        n = board.length;
        m = board[0].length;
        checkPath = new boolean[n][m];


        // 预处理
        // 寻找第一个字符
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i >= 0 && i < n &&
                        j >= 0 && j < m && !checkPath[i][j] 
                        && board[i][j] == word.charAt(0)) {
                            // 走过了就置为 true
                            checkPath[i][j] = true;

                            // 一旦成功直接返回 true
                            if(dfs(board,word,i,j,1)) {
                                return true;
                            }

                            // 失败了就重新置为 false
                            checkPath[i][j] = false;
                }
            }
        }

        // 遍历完都没找到
        return false;

    }

    private boolean dfs(char[][] board, String word, int x, int y, int pos) {
        // 递归出口， 找到就返回
        if (pos == word.length()) {
            return true;
        }

        // 进行四路递归
        for (int i = 0; i < 4; i++) {
 
                int r = x + row[i];
                int c = y + col[i];

                // 剪枝
                if (r >= 0 && r < n &&
                        c >= 0 && c < m 
                        && !checkPath[r][c] 
                        && board[r][c] == word.charAt(pos)) {
                            // 走过了就置为 true
                            checkPath[r][c] = true;

                            // 一旦查找到就返回
                            if(dfs(board,word,r,c,pos+1)) {
                                    return true;
                            }

                            // 恢复现场
                            checkPath[r][c] = false;
                            
                }
            
        }

        // 如果每找到就返回 false
        return false;

    }
}

/**
 * 题目：广搜_黄金矿工
 */

class Solution1 {

    // 坐标走起
    private int[] m = {0,0,-1,1};
    private int[] n = {-1,1,0,0};

    // 记录是否走过
    private  boolean[][] checkPath ;

    // 宽与长
    private int row ;
    private int col;

    int ret ;

    public int getMaximumGold(int[][] grid) {
        // 初始化
        row = grid.length;
        col = grid[0].length;
        checkPath = new boolean[row][col];
        ret = 0;

        // 寻找入口
        for(int i =0; i < row ; i++) {
            for(int j =0; j< col ; j++) {

                // 入口条件
                if(grid[i][j] != 0) {
                    // 记录是否走过
                    checkPath[i][j] = true;

                    // 开始递归
                    dfs(grid,i,j, grid[i][j]);

                    // 恢复现场
                    checkPath[i][j] = false;
                }
            }
        }

        return ret;
    }

    private void dfs(int[][] grid, int r , int  c , int sum ) {
        // 收集最大值
        ret = Math.max(sum , ret);

        // 直接深搜
        for(int i =0; i< 4; i++) {
            int x = r + m[i];
            int y = c + n[i];

            // 进行剪枝
            if(x >= 0 && x < row
                    && y >= 0 && y < col &&
                    !checkPath[x][y]  && grid[x][y] != 0) {
                checkPath[x][y] = true;
                dfs(grid, x,y, sum + grid[x][y]);



                // 还原现场
                checkPath[x][y] = false;
            }

        }
    }
}


/**
 * 题目： 广搜_不同路径（三）
 */

class Solution2 {

    // 方向移动
    int[] n = {0,0,-1,1};
    int[] m = {-1,1,0,0};

    boolean[][] checkPath;

    // 长和宽
    int row;
    int col;

    // 记录结果
    int  ret ;

    // 记录要走的步数
    int step ;

    public int uniquePathsIII(int[][] grid) {
        // 初始化
        row = grid.length;
        col = grid[0].length;
        step= 1;
        checkPath = new boolean[row][col];

        for(int i =0; i < row ; i++) {
            for(int j= 0; j<col ;j++) {
                if(grid[i][j] == 0) {
                    step++;
                }
            }
        }




        // 寻找起始位置
        for(int i =0; i < row ; i++) {
            for(int j= 0; j<col ;j++) {
                if(grid[i][j] == 1) {
                    checkPath[i][j] = true;

                    // 开始递归
                    dfs(grid,i,j, 0);

                    // 找到后直接返回结果
                    return ret;
                }
            }
        }



        return ret;
    }

    private void dfs(int[][] grid, int r, int c, int count) {
        // 递归出口
        if(grid[r][c] == 2) {

            // 根据步数是否想等
            // 实际步数 和 需要走完的步数
            if(count == step) {
                ret++;
            }

            return;
        }

        // 四个方位
        for(int i =0; i<4; i++) {
            int x = r + n[i];
            int y = c + m[i];

            // 剪枝
            if(x >= 0 && x < row && y >= 0 && y < col
                    && !checkPath[x][y] && grid[x][y] != -1) {
                // 深搜
                checkPath[x][y] = true;
                dfs(grid, x, y, count+1);

                // 恢复现场
                checkPath[x][y] = false;

            }
        }
    }
}


/**
 *
 * 题目: 广搜_图像渲染
 *
 */

class Solution3 {

    // 方位
    int[] n = {0,0,-1,1};
    int[] m = {-1,1,0,0};

    // 长与宽
    int row ;
    int col ;

    // 起始数字
    int again;

    // 路径途径
    boolean[][] checkPath;

    // 存储结果
    int[][] ret;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {

        // 初始化
        row = image.length;
        col = image[0].length;
        again = image[sr][sc];
        ret = new int[row][col];
        checkPath = new boolean[row][col];

        // 先拷贝
        for(int i =0; i<row ; i++) {
            for(int j = 0; j<col ; j++) {
                ret[i][j] = image[i][j];
            }
        }

        // 修改自身
        ret[sr][sc]= color;

        // 开始递归
        dfs(image, sr,sc, color);

        return ret;
    }

    private void dfs(int[][] image, int x, int y , int aim) {

        // 方位移动
        for(int i =0; i<4; i++) {
            int r = x + n[i];
            int c = y + m[i];

            // 剪枝
            if(r >= 0 && r < row
                    && c >= 0 && c < col
                    && !checkPath[r][c]
                    && image[r][c] == again) {

                ret[r][c] = aim;
                checkPath[r][c] = true;

                dfs(image, r, c, aim);
            }
        }
    }
}


/**
 * 题目： floodfill_岛屿数量
 */

class Solution4 {

    // 方位
    int[] n = { 0, 0, -1, 1 };
    int[] m = { -1, 1, 0, 0 };

    // 长与宽
    int row;
    int col;

    // 路径痕迹
    boolean[][] checkPath;

    // 收集结果
    int ret;

    public int numIslands(char[][] grid) {

        // 初始化
        row = grid.length;
        col = grid[0].length;
        checkPath = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 外部收集
                if (!checkPath[i][j] && grid[i][j] == '1') {
                    // 这个位置先放置为 true
                    checkPath[i][j] = true;

                    // 开始递归， 把所有相同集群全都确认掉
                    dfs(grid, i, j);

                    // 最后集群+ 1
                    ret++;
                }
            }
        }

        return ret;
    }

    private void dfs(char[][] grid, int r, int c) {

        // 方位 移动
        for (int i = 0; i < 4; i++) {
            int x = r + n[i];
            int y = c + m[i];

            // 剪枝
            if(x>= 0 && x < row
                    && y>= 0 && y < col
                    && !checkPath[x][y] && grid[x][y] == '1') {
                // 这个位置先放置为 true
                checkPath[x][y] = true;

                // 开始递归， 把所有该集群全都确认掉
                dfs(grid,  x, y);
            }
        }
    }
}


/**
 * 题目： floodFill_岛屿面积
 */

class Solution5 {

    // 方位
    int[] n = {0,0,-1,1};
    int[] m = {-1,1,0,0};

    // 长 和 宽
    int row ;
    int col;

    // 路径痕迹
    boolean[][] checkPath;

    // 记录结果
    int ret;


    int sum;

    public int maxAreaOfIsland(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        checkPath = new boolean[row][col];


        for(int i =0; i < row ; i++) {
            for(int j = 0; j<col ; j++) {
                // 筛选
                if(grid[i][j] == 1 && !checkPath[i][j]) {
                    sum =1;

                    // 记录当下
                    checkPath[i][j] = true;


                    // 开始递归
                    dfs(grid, i, j);


                }
            }
        }


        return ret ;
    }

    private void dfs(int[][] grid , int index , int pos ) {

        // 更新结果
        ret = Math.max(sum , ret);


        // 方位移动
        for(int i =0; i < 4; i++) {
            int x = index + n[i];
            int y = pos + m[i] ;

            // 剪枝
            if(x>= 0 && x<row
                    && y>= 0 &&  y< col
                    && grid[x][y] == 1 &&  !checkPath[x][y] ) {
                checkPath[x][y] = true;
                // 记录岛屿数
                sum++;

                // 深搜
                dfs(grid, x, y);
            }

        }
    }



}


/**
 * 题目： floodFill_被环绕的面积
 */

class Solution6 {

    // 方位
    int[] n = { 0, 0, -1, 1 };
    int[] m = { -1, 1, 0, 0 };

    // 路径痕迹
    boolean[][] checkPath;


    // 长和宽
    int row;
    int col;

    public void solve(char[][] board) {

        // 初始化
        row = board.length;
        col = board[0].length;
        checkPath = new boolean[row][col];

        // 查找区域
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {

                // 先处理边界
                if((i == 0 || i == row -1
                        || j == col -1 || j == 0)
                        && (board[i][j] == 'O' && !checkPath[i][j])) {
                    // 开始递归
                    checkPath[i][j] = true;
                    dfs(board,i,j);
                }

            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O' && !checkPath[i][j]) {
                    board[i][j] = 'X';
                }
            }
        }
    }


    private void dfs(char[][] board, int index, int pos ) {



        // 路径移动
        for(int k =0; k < 4; k++) {
            int i = index + n[k];
            int j = pos + m[k];

            // 剪枝
            if(i >= 0 &&  i < row
                    && j >= 0 && j < col
                    && !checkPath[i][j] && board[i][j] == 'O') {
                checkPath[i][j] = true;

                // 传递遇到边界的情况
                dfs(board, i,j) ;

            }
        }



    }
}

